
//二分查找数
class Node{
    constructor(node){
        this.node=node
        this.node.left=null
        this.node.right=null
        this.count=0
        this.index=-1
    }
    
    insert({key,value},node){
       if(node==null){
           this.count++
           return new Node({key,value}).node
       }
       if(key==node.key){
           node.value=value
           return 
       }else if(key>node.key){
           node.right=this.insert({key,value},node.right)
       }else{
           node.left=this.insert({key,value},node.left)
       }
       return node
    }
    search(tar,node){
       if(!node) return this.index=-1

       if(tar==node.value){
           return this.index=node.key
       }else if(tar>node.key){
           this.search(tar,node.left)
       }else{
           this.search(tar,node.right)
       }
    }
    searchMin(node){
      if(!node) return
      if(!node.left){
          return node
      }
      this.searchMin(node.left)
    }
    searchMax(node){
        if(!node) return 
        if(!node.right){
            return node
        }
        this.searchMax(node.right)
    }
    fontEach(node){
        if(node){
            console.log(node.key)
            this.fontEach(node.left)
            this.fontEach(node.right)
        }
    }
    cenEach(node){
        if(node){
            this.cenEach(node.left)
            console.log(node.key)
            this.cenEach(node.right)
        }
    }
    bottomEach(node){
        if(node){
            this.bottomEach(node.left)
            this.bottomEach(node.right)
            console.log(node.key)
        }
    }
    guanEach(node){
        let res=[]
        let dl=[]
        let root=node
        dl.push(root)
        while(dl.length>0){
          let n=dl.shift()
          res.push(n.key)
          n.left&&dl.push(n.left)
          n.right&&dl.push(n.right)
        }
        console.log(res)
    }
    removeMin(node){
        if(!node) return
        if(!node.left){
            return node.right
        }
        node.left=this.removeMin(node.left)
        return node
    }
    removeMax(node){
        if(!node) return
        if(!node.right){
            return node.left
        }
        node.right=this.removeMax(node.right)
        return node
    }
    removeNode(node,key){
        if(!node) return 
        if(key>node.key){
            node.right=this.removeNode(node.right,key)
            return node
        }else if(key<node.key){
            node.left=this.removeNode(node.left)
            return node
        }else{
            if(!node.left){
                return node.right
            }
            if(!node.right){
                return node.left
            }
            let oriNode=null
           
            oriNode=this.searchMin(node.right)
            let snode=this.removeMin(node.right)
            let newNode=new Node({key:oriNode.key,value:oriNode.value}).node
            newNode.left=node.left
            newNode.right=snode
            node=newNode
            return node
        }
    }

}

let n=new Node({key:10,value:10})
n.insert({key:23,value:23},n.node)
n.insert({key:3,value:3},n.node)
n.insert({key:12,value:12},n.node)
n.insert({key:11,value:11},n.node)
n.insert({key:18,value:18},n.node)
n.insert({key:8,value:8},n.node)
n.insert({key:4,value:4},n.node)
n.insert({key:20,value:20},n.node)

console.log(n.node)
n.guanEach(n.node)
// n.removeNode(n.node,12)

// n.fontEach(n.node)